package lib

func QuickSort(arr []int, low, high int) {
	//排除参数传入错误的情况以及数组传入长度不足2，没有必要排序的情况
	if len(arr) < 2 || low > high || high <= 0 || low < 0 {
		return
	}

	left, right := low, high
	pivot := arr[left]

	for left < right {
		for right > left && arr[right] >= pivot {
			right--
		}

		if right > left {
			arr[left] = arr[right]
		}

		for left < right && arr[left] < pivot {
			left++
		}

		if left < right {
			arr[right] = arr[left]
		}

		if left <= right {
			arr[left] = pivot
		}
	}

	//对左边进行排序
	QuickSort(arr, low, right-1)
	//对右边进行排序
	QuickSort(arr, right+1, high)
}

func QuickSortV2(arr []int, low, high int) {
	if low >= high {
		return
	}

	left, right := low, high
	pivot := arr[(low+high)/2] // 这里的经验值取的是中间数，经过 Benchmark 测试，确实比较优秀

	for left <= right {
		// 从左边开始迭代

		// 左边的数如果比 pivot 小，那么就应该将他放在左边，继续向右滑动，遇到一个比他大的为止
		for arr[left] < pivot {
			left++
		}

		// 右边的数如果比 pivot 大，那么就应该将他放在右边，继续向左滑动，遇到一个比他小的为止
		for arr[right] > pivot {
			right--
		}

		// 这里进行一次交换，将上面碰到的大数和小数交换一次
		//left 继续右走，right 继续左走 注意这里还不一定相遇，去继续执行上面的逻辑
		if left <= right {
			arr[left], arr[right] = arr[right], arr[left]
			left++
			right--
		}
	}

	QuickSortV2(arr, low, right)
	QuickSortV2(arr, left, high)
}
